# -*- coding: utf-8 -*-

# __date:       2021/7/13
# __author:     Yang Chao
# __function:

class Solution:

    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 找出链表的长度
        ln = 0
        temp = head
        while temp:
            ln += 1
            temp = temp.next

        # 然后找下一个节点
        cu = ln - n
        if cu == 0:
            return head.next

        temp = head
        while cu > 1:
            cu -= 1
            temp = temp.next
        temp.next = temp.next.next
        return head

    def removeNthFromEnd2(self, head: ListNode, n: int) -> ListNode:
        # 双指针求解
        dummy = ListNode(-1)
        dummy.next = head
        p, q = dummy, dummy

        # 先让p指针先走n个点
        for i in range(n):
            p = p.next

        # 当前走了n不的p指针走到头了，q指针刚好停在到处第n个位置
        while p.next:
            p = p.next
            q = q.next

        q.next = q.next.next
        return dummy.next